package Offer.offer2017;

/**
 * 第n个丑数
 * Created by 雷文康 on 2018/1/3.
 */
public class Test34 {
    public static void main(String[] args) {
        System.out.println(getUgly2(1500));
    }

    public static int getUgly(int n) {
        if (n < 0) {
            return -1;
        }
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (isUgly(num)) {
                count++;
            }
        }
        return num;
    }

    public static int getUgly2(int n) {
        if (n < 0) {
            return -1;
        }
        int[] array = new int[n];
        int count = 1;
        array[0] = 1;
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;
        while (count < n) {
            array[count] = min(array[index2] * 2, array[index3] * 3, array[index5] * 5);
            if (array[count] == array[index2] * 2) {
                index2++;
            }
            if (array[count] == array[index3] * 3) {
                index3++;
            }
            if (array[count] == array[index5] * 5) {
                index5++;
            }
            count++;
        }
        return array[count - 1];
    }

    private static int min(int a, int b, int c) {
        int min = a;
        if (b < min) {
            min = b;
        }
        if (c < min) {
            min = c;
        }
        return min;
    }

    private static boolean isUgly(int num) {
        while (num % 2 == 0) {
            num = num / 2;
        }
        while (num % 3 == 0) {
            num = num / 3;
        }
        while (num % 5 == 0) {
            num = num / 5;
        }
        return num == 1;
    }
}
